import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> ret = new ArrayList<>();
            for(int i = 0;i < nums.length;) {
                if(nums[i] > 0) break;
                int left = i+1;
                int right = nums.length - 1;
                int target = -nums[i];
                while(left < right) {
                    int sum = nums[left] +nums[right];
                    if(sum < target) {
                        left ++;
                    }else if(sum > target) {
                        right --;
                    }else {
                        List<Integer> list = new ArrayList<>();
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                        left ++;
                        right --;
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;

                    }
                }
                i ++;
                while(i < nums.length && nums[i] == nums[i-1]) i ++;
            }
            return ret;
        }
    }
}
